home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / More Source / C⁄C++ / Peter's Final Project / jpeg-5b / wrgif.c < prev    next >
Text File  |  1995-03-16  |  16KB  |  506 lines
  1. /*
  2.  * wrgif.c
  3.  *
  4.  * Copyright (C) 1991-1994, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  **************************************************************************
  9.  * WARNING: You will need an LZW patent license from Unisys in order to   *
  10.  * use this file legally in any commercial or shareware application.      *
  11.  **************************************************************************
  12.  *
  13.  * This file contains routines to write output images in GIF format.
  14.  *
  15.  * These routines may need modification for non-Unix environments or
  16.  * specialized applications.  As they stand, they assume output to
  17.  * an ordinary stdio stream.
  18.  */
  19.  
  20. /*
  21.  * This code is loosely based on ppmtogif from the PBMPLUS distribution
  22.  * of Feb. 1991.  That file contains the following copyright notice:
  23.  *    Based on GIFENCODE by David Rowley <mgardi@watdscu.waterloo.edu>.
  24.  *    Lempel-Ziv compression based on "compress" by Spencer W. Thomas et al.
  25.  *    Copyright (C) 1989 by Jef Poskanzer.
  26.  *    Permission to use, copy, modify, and distribute this software and its
  27.  *    documentation for any purpose and without fee is hereby granted, provided
  28.  *    that the above copyright notice appear in all copies and that both that
  29.  *    copyright notice and this permission notice appear in supporting
  30.  *    documentation.  This software is provided "as is" without express or
  31.  *    implied warranty.
  32.  *
  33.  * We are also required to state that
  34.  *    "The Graphics Interchange Format(c) is the Copyright property of
  35.  *    CompuServe Incorporated. GIF(sm) is a Service Mark property of
  36.  *    CompuServe Incorporated."
  37.  */
  38.  
  39. #include "cdjpeg.h"        /* Common decls for cjpeg/djpeg applications */
  40.  
  41. #ifdef GIF_SUPPORTED
  42.  
  43.  
  44. #define    MAX_LZW_BITS    12    /* maximum LZW code size (4096 symbols) */
  45.  
  46. typedef INT16 code_int;        /* must hold -1 .. 2**MAX_LZW_BITS */
  47.  
  48. #define LZW_TABLE_SIZE    ((code_int) 1 << MAX_LZW_BITS)
  49.  
  50. #define HSIZE        5003    /* hash table size for 80% occupancy */
  51.  
  52. typedef int hash_int;        /* must hold -2*HSIZE..2*HSIZE */
  53.  
  54. #define MAXCODE(n_bits)    (((code_int) 1 << (n_bits)) - 1)
  55.  
  56.  
  57. /*
  58.  * The LZW hash table consists of two parallel arrays:
  59.  *   hash_code[i]    code of symbol in slot i, or 0 if empty slot
  60.  *   hash_value[i]    symbol's value; undefined if empty slot
  61.  * where slot values (i) range from 0 to HSIZE-1.  The symbol value is
  62.  * its prefix symbol's code concatenated with its suffix character.
  63.  *
  64.  * Algorithm:  use open addressing double hashing (no chaining) on the
  65.  * prefix code / suffix character combination.  We do a variant of Knuth's
  66.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  67.  * secondary probe.
  68.  *
  69.  * The hash_value[] table is allocated from FAR heap space since it would
  70.  * use up rather a lot of the near data space in a PC.
  71.  */
  72.  
  73. typedef INT32 hash_entry;    /* must hold (code_int<<8) | byte */
  74.  
  75. #define HASH_ENTRY(prefix,suffix)  ((((hash_entry) (prefix)) << 8) | (suffix))
  76.  
  77.  
  78. /* Private version of data destination object */
  79.  
  80. typedef struct {
  81.   struct djpeg_dest_struct pub;    /* public fields */
  82.  
  83.   j_decompress_ptr cinfo;    /* back link saves passing separate parm */
  84.  
  85.   /* State for packing variable-width codes into a bitstream */
  86.   int n_bits;            /* current number of bits/code */
  87.   code_int maxcode;        /* maximum code, given n_bits */
  88.   int init_bits;        /* initial n_bits ... restored after clear */
  89.   INT32 cur_accum;        /* holds bits not yet output */
  90.   int cur_bits;            /* # of bits in cur_accum */
  91.  
  92.   /* LZW string construction */
  93.   code_int waiting_code;    /* symbol not yet output; may be extendable */
  94.   boolean first_byte;        /* if TRUE, waiting_code is not valid */
  95.  
  96.   /* State for LZW code assignment */
  97.   code_int ClearCode;        /* clear code (doesn't change) */
  98.   code_int EOFCode;        /* EOF code (ditto) */
  99.   code_int free_code;        /* first not-yet-used symbol code */
  100.  
  101.   /* LZW hash table */
  102.   code_int *hash_code;        /* => hash table of symbol codes */
  103.   hash_entry FAR *hash_value;    /* => hash table of symbol values */
  104.  
  105.   /* GIF data packet construction buffer */
  106.   int bytesinpkt;        /* # of bytes in current packet */
  107.   char packetbuf[256];        /* workspace for accumulating packet */
  108.  
  109. } gif_dest_struct;
  110.  
  111. typedef gif_dest_struct * gif_dest_ptr;
  112.  
  113.  
  114. /*
  115.  * Routines to package compressed data bytes into GIF data blocks.
  116.  * A data block consists of a count byte (1..255) and that many data bytes.
  117.  */
  118.  
  119. LOCAL void
  120. flush_packet (gif_dest_ptr dinfo)
  121. /* flush any accumulated data */
  122. {
  123.   if (dinfo->bytesinpkt > 0) {    /* never write zero-length packet */
  124.     dinfo->packetbuf[0] = (char) dinfo->bytesinpkt++;
  125.     if (JFWRITE(dinfo->pub.output_file, dinfo->packetbuf, dinfo->bytesinpkt)
  126.     != (size_t) dinfo->bytesinpkt)
  127.       ERREXIT(dinfo->cinfo, JERR_FILE_WRITE);
  128.     dinfo->bytesinpkt = 0;
  129.   }
  130. }
  131.  
  132.  
  133. /* Add a character to current packet; flush to disk if necessary */
  134. #define CHAR_OUT(dinfo,c)  \
  135.     { (dinfo)->packetbuf[++(dinfo)->bytesinpkt] = (char) (c);  \
  136.         if ((dinfo)->bytesinpkt >= 255)  \
  137.           flush_packet(dinfo);  \
  138.     }
  139.  
  140.  
  141. /* Routine to convert variable-width codes into a byte stream */
  142.  
  143. LOCAL void
  144. output (gif_dest_ptr dinfo, code_int code)
  145. /* Emit a code of n_bits bits */
  146. /* Uses cur_accum and cur_bits to reblock into 8-bit bytes */
  147. {
  148.   dinfo->cur_accum |= ((INT32) code) << dinfo->cur_bits;
  149.   dinfo->cur_bits += dinfo->n_bits;
  150.  
  151.   while (dinfo->cur_bits >= 8) {
  152.     CHAR_OUT(dinfo, dinfo->cur_accum & 0xFF);
  153.     dinfo->cur_accum >>= 8;
  154.     dinfo->cur_bits -= 8;
  155.   }
  156.  
  157.   /*
  158.    * If the next entry is going to be too big for the code size,
  159.    * then increase it, if possible.  We do this here to ensure
  160.    * that it's done in sync with the decoder's codesize increases.
  161.    */
  162.   if (dinfo->free_code > dinfo->maxcode) {
  163.     dinfo->n_bits++;
  164.     if (dinfo->n_bits == MAX_LZW_BITS)
  165.       dinfo->maxcode = LZW_TABLE_SIZE; /* free_code will never exceed this */
  166.     else
  167.       dinfo->maxcode = MAXCODE(dinfo->n_bits);
  168.   }
  169. }
  170.  
  171.  
  172. /* The LZW algorithm proper */
  173.  
  174.  
  175. LOCAL void
  176. clear_hash (gif_dest_ptr dinfo)
  177. /* Fill the hash table with empty entries */
  178. {
  179.   /* It's sufficient to zero hash_code[] */
  180.   MEMZERO(dinfo->hash_code, HSIZE * SIZEOF(code_int));
  181. }
  182.  
  183.  
  184. LOCAL void
  185. clear_block (gif_dest_ptr dinfo)
  186. /* Reset compressor and issue a Clear code */
  187. {
  188.   clear_hash(dinfo);            /* delete all the symbols */
  189.   dinfo->free_code = dinfo->ClearCode + 2;
  190.   output(dinfo, dinfo->ClearCode);    /* inform decoder */
  191.   dinfo->n_bits = dinfo->init_bits;    /* reset code size */
  192.   dinfo->maxcode = MAXCODE(dinfo->n_bits);
  193. }
  194.  
  195.  
  196. LOCAL void
  197. compress_init (gif_dest_ptr dinfo, int i_bits)
  198. /* Initialize LZW compressor */
  199. {
  200.   /* init all the state variables */
  201.   dinfo->n_bits = dinfo->init_bits = i_bits;
  202.   dinfo->maxcode = MAXCODE(dinfo->n_bits);
  203.   dinfo->ClearCode = ((code_int) 1 << (i_bits - 1));
  204.   dinfo->EOFCode = dinfo->ClearCode + 1;
  205.   dinfo->free_code = dinfo->ClearCode + 2;
  206.   dinfo->first_byte = TRUE;    /* no waiting symbol yet */
  207.   /* init output buffering vars */
  208.   dinfo->bytesinpkt = 0;
  209.   dinfo->cur_accum = 0;
  210.   dinfo->cur_bits = 0;
  211.   /* clear hash table */
  212.   clear_hash(dinfo);
  213.   /* GIF specifies an initial Clear code */
  214.   output(dinfo, dinfo->ClearCode);
  215. }
  216.  
  217.  
  218. LOCAL void
  219. compress_byte (gif_dest_ptr dinfo, int c)
  220. /* Accept and compress one 8-bit byte */
  221. {
  222.   register hash_int i;
  223.   register hash_int disp;
  224.   register hash_entry probe_value;
  225.  
  226.   if (dinfo->first_byte) {    /* need to initialize waiting_code */
  227.     dinfo->waiting_code = c;
  228.     dinfo->first_byte = FALSE;
  229.     return;
  230.   }
  231.  
  232.   /* Probe hash table to see if a symbol exists for
  233.    * waiting_code followed by c.
  234.    * If so, replace waiting_code by that symbol and return.
  235.    */
  236.   i = ((hash_int) c << (MAX_LZW_BITS-8)) + dinfo->waiting_code;
  237.   /* i is less than twice 2**MAX_LZW_BITS, therefore less than twice HSIZE */
  238.   if (i >= HSIZE)
  239.     i -= HSIZE;
  240.  
  241.   probe_value = HASH_ENTRY(dinfo->waiting_code, c);
  242.   
  243.   if (dinfo->hash_code[i] != 0) { /* is first probed slot empty? */
  244.     if (dinfo->hash_value[i] == probe_value) {
  245.       dinfo->waiting_code = dinfo->hash_code[i];
  246.       return;
  247.     }
  248.     if (i == 0)            /* secondary hash (after G. Knott) */
  249.       disp = 1;
  250.     else
  251.       disp = HSIZE - i;
  252.     for (;;) {
  253.       i -= disp;
  254.       if (i < 0)
  255.     i += HSIZE;
  256.       if (dinfo->hash_code[i] == 0)
  257.     break;            /* hit empty slot */
  258.       if (dinfo->hash_value[i] == probe_value) {
  259.     dinfo->waiting_code = dinfo->hash_code[i];
  260.     return;
  261.       }
  262.     }
  263.   }
  264.  
  265.   /* here when hashtable[i] is an empty slot; desired symbol not in table */
  266.   output(dinfo, dinfo->waiting_code);
  267.   if (dinfo->free_code < LZW_TABLE_SIZE) {
  268.     dinfo->hash_code[i] = dinfo->free_code++; /* add symbol to hashtable */
  269.     dinfo->hash_value[i] = probe_value;
  270.   } else
  271.     clear_block(dinfo);
  272.   dinfo->waiting_code = c;
  273. }
  274.  
  275.  
  276. LOCAL void
  277. compress_term (gif_dest_ptr dinfo)
  278. /* Clean up at end */
  279. {
  280.   /* Flush out the buffered code */
  281.   if (! dinfo->first_byte)
  282.     output(dinfo, dinfo->waiting_code);
  283.   /* Send an EOF code */
  284.   output(dinfo, dinfo->EOFCode);
  285.   /* Flush the bit-packing buffer */
  286.   if (dinfo->cur_bits > 0) {
  287.     CHAR_OUT(dinfo, dinfo->cur_accum & 0xFF);
  288.   }
  289.   /* Flush the packet buffer */
  290.   flush_packet(dinfo);
  291. }
  292.  
  293.  
  294. /* GIF header construction */
  295.  
  296.  
  297. LOCAL void
  298. put_word (gif_dest_ptr dinfo, unsigned int w)
  299. /* Emit a 16-bit word, LSB first */
  300. {
  301.   putc(w & 0xFF, dinfo->pub.output_file);
  302.   putc((w >> 8) & 0xFF, dinfo->pub.output_file);
  303. }
  304.  
  305.  
  306. LOCAL void
  307. put_3bytes (gif_dest_ptr dinfo, int val)
  308. /* Emit 3 copies of same byte value --- handy subr for colormap construction */
  309. {
  310.   putc(val, dinfo->pub.output_file);
  311.   putc(val, dinfo->pub.output_file);
  312.   putc(val, dinfo->pub.output_file);
  313. }
  314.  
  315.  
  316. LOCAL void
  317. emit_header (gif_dest_ptr dinfo, int num_colors, JSAMPARRAY colormap)
  318. /* Output the GIF file header, including color map */
  319. /* If colormap==NULL, synthesize a gray-scale colormap */
  320. {
  321.   int BitsPerPixel, ColorMapSize, InitCodeSize, FlagByte;
  322.   int cshift = dinfo->cinfo->data_precision - 8;
  323.   int i;
  324.  
  325.   if (num_colors > 256)
  326.     ERREXIT1(dinfo->cinfo, JERR_TOO_MANY_COLORS, num_colors);
  327.   /* Compute bits/pixel and related values */
  328.   BitsPerPixel = 1;
  329.   while (num_colors > (1 << BitsPerPixel))
  330.     BitsPerPixel++;
  331.   ColorMapSize = 1 << BitsPerPixel;
  332.   if (BitsPerPixel <= 1)
  333.     InitCodeSize = 2;
  334.   else
  335.     InitCodeSize = BitsPerPixel;
  336.   /*
  337.    * Write the GIF header.
  338.    * Note that we generate a plain GIF87 header for maximum compatibility.
  339.    */
  340.   putc('G', dinfo->pub.output_file);
  341.   putc('I', dinfo->pub.output_file);
  342.   putc('F', dinfo->pub.output_file);
  343.   putc('8', dinfo->pub.output_file);
  344.   putc('7', dinfo->pub.output_file);
  345.   putc('a', dinfo->pub.output_file);
  346.   /* Write the Logical Screen Descriptor */
  347.   put_word(dinfo, (unsigned int) dinfo->cinfo->output_width);
  348.   put_word(dinfo, (unsigned int) dinfo->cinfo->output_height);
  349.   FlagByte = 0x80;        /* Yes, there is a global color table */
  350.   FlagByte |= (BitsPerPixel-1) << 4; /* color resolution */
  351.   FlagByte |= (BitsPerPixel-1);    /* size of global color table */
  352.   putc(FlagByte, dinfo->pub.output_file);
  353.   putc(0, dinfo->pub.output_file); /* Background color index */
  354.   putc(0, dinfo->pub.output_file); /* Reserved (aspect ratio in GIF89) */
  355.   /* Write the Global Color Map */
  356.   /* If the color map is more than 8 bits precision, */
  357.   /* we reduce it to 8 bits by shifting */
  358.   for (i=0; i < ColorMapSize; i++) {
  359.     if (i < num_colors) {
  360.       if (colormap != NULL) {
  361.     if (dinfo->cinfo->out_color_space == JCS_RGB) {
  362.       /* Normal case: RGB color map */
  363.       putc(GETJSAMPLE(colormap[0][i]) >> cshift, dinfo->pub.output_file);
  364.       putc(GETJSAMPLE(colormap[1][i]) >> cshift, dinfo->pub.output_file);
  365.       putc(GETJSAMPLE(colormap[2][i]) >> cshift, dinfo->pub.output_file);
  366.     } else {
  367.       /* Grayscale "color map": possible if quantizing grayscale image */
  368.       put_3bytes(dinfo, GETJSAMPLE(colormap[0][i]) >> cshift);
  369.     }
  370.       } else {
  371.     /* Create a gray-scale map of num_colors values, range 0..255 */
  372.     put_3bytes(dinfo, (i * 255 + (num_colors-1)/2) / (num_colors-1));
  373.       }
  374.     } else {
  375.       /* fill out the map to a power of 2 */
  376.       put_3bytes(dinfo, 0);
  377.     }
  378.   }
  379.   /* Write image separator and Image Descriptor */
  380.   putc(',', dinfo->pub.output_file); /* separator */
  381.   put_word(dinfo, 0);        /* left/top offset */
  382.   put_word(dinfo, 0);
  383.   put_word(dinfo, (unsigned int) dinfo->cinfo->output_width); /* image size */
  384.   put_word(dinfo, (unsigned int) dinfo->cinfo->output_height);
  385.   /* flag byte: not interlaced, no local color map */
  386.   putc(0x00, dinfo->pub.output_file);
  387.   /* Write Initial Code Size byte */
  388.   putc(InitCodeSize, dinfo->pub.output_file);
  389.  
  390.   /* Initialize for LZW compression of image data */
  391.   compress_init(dinfo, InitCodeSize+1);
  392. }
  393.  
  394.  
  395. /*
  396.  * Startup: write the file header.
  397.  */
  398.  
  399. METHODDEF void
  400. start_output_gif (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo)
  401. {
  402.   gif_dest_ptr dest = (gif_dest_ptr) dinfo;
  403.  
  404.   if (cinfo->quantize_colors)
  405.     emit_header(dest, cinfo->actual_number_of_colors, cinfo->colormap);
  406.   else
  407.     emit_header(dest, 256, (JSAMPARRAY) NULL);
  408. }
  409.  
  410.  
  411. /*
  412.  * Write some pixel data.
  413.  * In this module rows_supplied will always be 1.
  414.  */
  415.  
  416. METHODDEF void
  417. put_pixel_rows (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo,
  418.         JDIMENSION rows_supplied)
  419. {
  420.   gif_dest_ptr dest = (gif_dest_ptr) dinfo;
  421.   register JSAMPROW ptr;
  422.   register JDIMENSION col;
  423.  
  424.   ptr = dest->pub.buffer[0];
  425.   for (col = cinfo->output_width; col > 0; col--) {
  426.     compress_byte(dest, GETJSAMPLE(*ptr++));
  427.   }
  428. }
  429.  
  430.  
  431. /*
  432.  * Finish up at the end of the file.
  433.  */
  434.  
  435. METHODDEF void
  436. finish_output_gif (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo)
  437. {
  438.   gif_dest_ptr dest = (gif_dest_ptr) dinfo;
  439.  
  440.   /* Flush LZW mechanism */
  441.   compress_term(dest);
  442.   /* Write a zero-length data block to end the series */
  443.   putc(0, dest->pub.output_file);
  444.   /* Write the GIF terminator mark */
  445.   putc(';', dest->pub.output_file);
  446.   /* Make sure we wrote the output file OK */
  447.   fflush(dest->pub.output_file);
  448.   if (ferror(dest->pub.output_file))
  449.     ERREXIT(cinfo, JERR_FILE_WRITE);
  450. }
  451.  
  452.  
  453. /*
  454.  * The module selection routine for GIF format output.
  455.  */
  456.  
  457. GLOBAL djpeg_dest_ptr
  458. jinit_write_gif (j_decompress_ptr cinfo)
  459. {
  460.   gif_dest_ptr dest;
  461.  
  462.   /* Create module interface object, fill in method pointers */
  463.   dest = (gif_dest_ptr)
  464.       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  465.                   SIZEOF(gif_dest_struct));
  466.   dest->cinfo = cinfo;        /* make back link for subroutines */
  467.   dest->pub.start_output = start_output_gif;
  468.   dest->pub.put_pixel_rows = put_pixel_rows;
  469.   dest->pub.finish_output = finish_output_gif;
  470.  
  471.   if (cinfo->out_color_space != JCS_GRAYSCALE &&
  472.       cinfo->out_color_space != JCS_RGB)
  473.     ERREXIT(cinfo, JERR_GIF_COLORSPACE);
  474.  
  475.   /* Force quantization if color or if > 8 bits input */
  476.   if (cinfo->out_color_space != JCS_GRAYSCALE || cinfo->data_precision > 8) {
  477.     /* Force quantization to at most 256 colors */
  478.     cinfo->quantize_colors = TRUE;
  479.     if (cinfo->desired_number_of_colors > 256)
  480.       cinfo->desired_number_of_colors = 256;
  481.   }
  482.  
  483.   /* Calculate output image dimensions so we can allocate space */
  484.   jpeg_calc_output_dimensions(cinfo);
  485.  
  486.   if (cinfo->output_components != 1) /* safety check: just one component? */
  487.     ERREXIT(cinfo, JERR_GIF_BUG);
  488.  
  489.   /* Create decompressor output buffer. */
  490.   dest->pub.buffer = (*cinfo->mem->alloc_sarray)
  491.     ((j_common_ptr) cinfo, JPOOL_IMAGE, cinfo->output_width, (JDIMENSION) 1);
  492.   dest->pub.buffer_height = 1;
  493.  
  494.   /* Allocate space for hash table */
  495.   dest->hash_code = (code_int *)
  496.     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  497.                 HSIZE * SIZEOF(code_int));
  498.   dest->hash_value = (hash_entry FAR *)
  499.     (*cinfo->mem->alloc_large) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  500.                 HSIZE * SIZEOF(hash_entry));
  501.  
  502.   return (djpeg_dest_ptr) dest;
  503. }
  504.  
  505. #endif /* GIF_SUPPORTED */
  506.